#include<vector>
#include<algorithm>
using std::max;
using std::vector;

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        // 数组两端插入1
        vector<int> val(nums.size()+2, 1);
        for (int i = 0; i < n; i++) val[i+1] = nums[i];
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); // dp[i][j] 代表 (i, j)区间值
        
        // 按照对角线进行遍历
        for (int s = 2; s < n+2; s++) {
            for (int i = 0; i < n+2-s; i++) {
                for (int k = i+1; k < i+s; k++) {
                    int sum = val[i] * val[i+s] * val[k];
                    sum += (dp[i][k] + dp[k][i+s]);
                    dp[i][i+s] = max(dp[i][i+s], sum);
                }
            }
        }


        return dp[0][n+1];


    }
};